from operator import itemgetter
from collections import defaultdict


# Input

index = dict()  # Map from IATA to id
n = 0  # Number of ids
iatas, names, coords = [], [], []
with open('airports.txt') as fp:
    ID, NAME, CITY, COUNTRY, IATA, ICAO, LAT, LON = range(8)
    for line in fp.read().split('\n')[:-1]:
        l = line.split(',')
        # Keep only airports with a known IATA code.
        iata, name = l[IATA], l[NAME].replace('\\', '').replace('\'', '')
        if iata:
            index[iata] = n
            iatas.append(iata)
            names.append(name)
            n += 1
            try:
                coords.append((float(l[LAT]), float(l[LON])))
            except:
                coords.append((0, 0))

depart = [0] * n  # Count departures
arrive = [0] * n  # Count arrivals
routes = defaultdict(lambda: defaultdict(int))  # Map <origin, destiny, count>
with open('routes.txt') as fp:
    AIR_CODE, AIR_ID, ORIG_CODE, ORIG_ID, DEST_CODE, DEST_ID = range(6)
    for line in fp.read().split('\n')[:-1]:
        l = line.split(',')
        ocode, dcode = l[ORIG_CODE], l[DEST_CODE]
        # Ignores airports that aren't in aiports.txt.
        if ocode in index and dcode in index:
            orig, dest = index[ocode], index[dcode]
            depart[orig] += 1
            routes[orig][dest] += 1
            arrive[dest] += 1


# Pagerank

pagerank = [1 / n] * n
for i in range(100):
    # print('iteration {:03}, {:.10f}'.format(i, pagerank[0]))
    q = [0] * n
    pool = 0  # Acumulated pagerank of airports without departures.

    for orig in range(n):
        # Split pagerank across destinations.
        if depart[orig] > 0:
            # There are routes from the airport, split proportionally.
            for dest in routes[orig]:
                q[dest] += routes[orig][dest] / depart[orig] * pagerank[orig]
        else:
            # No routes from this airport, split equally among every airport.
            # For efficiency, instead of adding it now, add it's pagerank to a
            # pool that is  distributed at the end of the iteration.
            pool += pagerank[orig]

    # Distribute pool accross all airports.
    for k in range(n):
        q[k] += 1 / n * pool

    # Apply dampening.
    d = .85
    for k in range(n):
        pagerank[k] = q[k] * d + (1 - d) / n

# Results

# Sort results by pagerank
ranking = sorted(zip(range(n), pagerank), key=itemgetter(1), reverse=True)

# Print ranking of results
print('pos    pagerank     name')
for i, (k, pr) in enumerate(ranking):
    msg = '[{:04}] {:.10f} {} {}'
    print(msg.format(i, pr, iatas[k], names[k]))
